Recursion is the process where by a method calls itself until an exit condition is met. Very useful, but also very easy to shoot yourself in the foot.

Recusion is used where a method processes items, finds more and calls itself to process the items it finds. An example would be a directory tree listing. It first scans the root of the C: drive, then calls itself for each directory found. If a subdirectory also contains directories another call to itself is made.

Recursion is also used in mathematics and scientific programming, node programming, artificial intelligence and some database applications.

Recursion is a good way of reusing code and processing multiple levels of data, however it is very easy for the system to run away. You also need to pass data to the method that can get memory intensive. It will also have an impact on performance.

The following code sample illustrates a recursive method for listing a directory structure.

class Program
{
  static void Main()
  {
    StringBuilder dirList = new StringBuilder();

    dirList = directoryListing("c:/Inetpub", "");
    Console.WriteLine(dirList.ToString());
  }

  static StringBuilder directoryListing(string path, string indend)
  {
    StringBuilder result = new StringBuilder();
    DirectoryInfo di = new DirectoryInfo(path);
    DirectoryInfo[] directories = di.GetDirectories();

    foreach (DirectoryInfo dir in directories)
    {
      result.AppendLine(indent + dir.Name);
 
      // Call the method again on the directories found
      result.Append(directoryListing(dir.FullName, indent + "..").ToString());
    }
    return result;
  }
}

This routine will scan through the directory specified in the Main method, grab all the sub directories within that directory, add them to the result, then call itself on each of the subdirectories found. It will recurse until a folder has no subdirectories. Finally it returns the result back to the line that called the recursive method, until there are no more recursions to be processed. The result is then handed back to the Main method call.

Each time the recursive method is called you need to tell it where to start from, in this case the folder to look in. In this example I also use a parameter for the indent level. Each recursion adds two dots to the previous indent level so you can see the directory structure clearer.

It is very easy for a recursive method to run away with itself, an invalid parameter or start point will cause the method to call itself over and over again and never progress. In this case you will receive a StackOverflowException, which should be handled with a try catch block on the first call of the method.

 

Tutorials in this Series